// https://www.lintcode.com/problem/surrounded-regions/description


class Solution {
public:
    /*
     * @param board: board a 2D board containing 'X' and 'O'
     * @return: nothing
     */
    
    // 作废
    // void surroundedRegions(vector<vector<char>> &board) {
        // int len = board.size();
        // vector<vector<bool>> visited(len, vector<bool>(len, false));
        // int raw_x = 0;
        // int raw_y = 0;
        // bool find = false;
        // for (int i = 0; i < len && !find; ++i)
        // {
        //     for (int j = 0; j < len && !find; ++j)
        //     {
        //         if (board[i][j] == 'X')
        //         {
        //             raw_x = i;
        //             raw_y = j;
        //             find = true;
        //         }
        //     }
        // }
        // find = false;
        // int x = raw_x;
        // int y = raw_y;
        // while (!find)
        // {
        //     bool end = false;
        //     for (int j = max(x - 1, 0); j <= x + 1 && j < len && !end; j++) 
        //     {
        //         for (int k = max(y - 1, 0); k <= y + 1 && k < len && !end; k++)
        //         {
        //             if (j == x && k == y)
        //             {
        //                 continue;
        //             }
        //             else if (board[j][k] == 'X' && !visited[j][k])
        //             {
        //                 x = j;
        //                 y = k;
        //                 visited[j][k] = true;
        //                 end = true;
        //             }
        //             else if (j = raw_x && k == raw_y)
        //             {
        //                 end = true;
        //                 find = true;
        //             }
        //         }
        //     }
        // }
        // for (int i = 0; i < len; ++i) 
        // {
        //     int cnt = 0;
        //     for (int j = 0; j < len; ++j)
        //     {
        //         if (cnt == 1 && board[i][j] == 'O')
        //         {
        //             board[i][j] = 'X';
        //         }
        //         else if (visited[i][j])
        //         {
        //             if (cnt == 0)
        //             {
        //                 cnt++;
        //             }
        //             else
        //             {
        //                 continue;
        //             }
        //         }
        //     }
        // }
    // }
    
    
    
    // • 找到所有被 ‘X’ 围绕的区域 → 找到被平原围绕的盆地? 
    // – 反向思维:找到没有被平原围绕的盆地
    // – 从4条边上的盆地开始注水
    // – 除了有水的点变成‘O’其他地方全变成‘X’
    // 法一：从四面各自开始向中间包围，分别BFS
    // 注意(x, y)和len_x, len_y各自含义
    // void DFS(vector<vector<char>> &board, int x, int y) 
    // {
    //     if (x < 0 || x >= board.size() || y < 0 || y >= board[0].size() || board[x][y] != 'O')
    //     {
    //         return;
    //     }
    //     board[x][y] = 'W';
    //     DFS(board, x - 1, y); 
    //     DFS(board, x, y - 1); 
    //     DFS(board, x, y + 1); 
    //     DFS(board, x + 1, y); 
    // }
    
   
    // void BFS(vector<vector<char>> &board, int x, int y) 
    // {
    //     if (board[x][y] != 'O')
    //     {
    //         return;
    //     }
    //     int n = board.size();
    //     int m = board[0].size();
    //     int dx[4] = {0, 1, 0, -1};
    //     int dy[4] = {1, 0, -1, 0};
    //     queue<int> qx;
    //     queue<int> qy;
    //     qx.push(x);
    //     qy.push(y);
    //     board[x][y] = 'W'; 
    //     while (!qx.empty())
    //     {
    //         int cx = qx.front();
    //         int cy = qy.front();
    //         qx.pop();
    //         qy.pop();
    //         for (int i = 0; i < 4; ++i)
    //         {
    //             int nx = cx + dx[i];
    //             int ny = cy + dy[i];
    //             if (nx >= 0 && nx < n && ny >= 0 && ny < m && board[nx][ny] == 'O')
    //             {
    //                 board[nx][ny] = 'W';
    //                 qx.push(nx);
    //                 qy.push(ny);
    //             }
    //         }
    //     }
    // }
    
    // struct Node {
    //     int x;
    //     int y;
    // };
    
    // void BFS(vector<vector<char>> &board, int x, int y) 
    // {
    //     if (board[x][y] != 'O')
    //     {
    //         return;
    //     }
    //     int n = board.size();
    //     int m = board[0].size();
    //     int dx[4] = {0, 1, 0, -1};
    //     int dy[4] = {1, 0, -1, 0};
    //     queue<Node> q;
    //     Node nd = {x, y};
    //     q.push(nd);
    //     board[x][y] = 'W'; 
    //     while (!q.empty())
    //     {
    //         Node cn = q.front();
    //         q.pop();
    //         for (int i = 0; i < 4; ++i)
    //         {
    //             int nx = cn.x + dx[i];
    //             int ny = cn.y + dy[i];
    //             if (nx >= 0 && nx < n && ny >= 0 && ny < m && board[nx][ny] == 'O')
    //             {
    //                 board[nx][ny] = 'W';
    //                 q.push(Node{nx, ny});
    //             }
    //         }
    //     }
    // }


    // void surroundedRegions(vector<vector<char>> &board) {
    //     if (board.size() <= 1)
    //     {
    //         return;
    //     }
    //     int len_x = board[0].size();
    //     int len_y = board.size();
    //     for (int i = 0; i < len_y; ++i)
    //     {
    //         BFS(board, i, 0);
    //         BFS(board, i, len_x - 1);
    //     }
    //     for (int i = 0; i < len_x; ++i)
    //     {
    //         BFS(board, 0, i);
    //         BFS(board, len_y - 1, i);
    //     }
    //     for (int i = 0; i < len_y; ++i)
    //     {
    //         for (int j = 0; j < len_x; ++j)
    //         {
    //             if (board[i][j] == 'O')
    //             {
    //                 board[i][j] = 'X';
    //             }
    //             else if (board[i][j] == 'W')
    //             {
    //                 board[i][j] = 'O';
    //             }   
    //         }
    //     }
    // }
    
    void BFS(vector<vector<char>> &board, int x, int y)
    {
        queue<int> q;
        
    }
    // 法二：整体的四周向中间BFS
    void surroundedRegions(vector<vector<char>> &board) 
    {
        if (board.size() <= 1)
        {
            return;
        }
        queue<int> q;
        int len_x = board[0].size();
        int len_y = board.size();
        for (int i = 0; i < len_y; ++i)
        {
            enqueue(q, i, 0, board);
            enqueue(q, i, len_x - 1, board);
        }
        for (int i = 0; i < len_x; ++i)
        {
            enqueue(q, 0, i, board);
            enqueue(q, len_y - 1, i, board);
        }
        while (!q.empty())
        {
            int n = q.front();
            q.pop();
            int x = n / board.size();
            int y = n % board.size();
            board[x][y] = 'W';
            enqueue(q, x - 1, y, board);
            enqueue(q, x + 1, y, board);
            enqueue(q, x, y - 1, board);
            enqueue(q, x, y + 1, board);
        }
        for (int i = 0; i < len_y; ++i)
        {
            for (int j = 0; j < len_x; ++j)
            {
                if (board[i][j] == 'O')
                {
                    board[i][j] = 'X';
                }
                else if (board[i][j] == 'W')
                {
                    board[i][j] = 'O';
                }   
            }
        }
    }
    
    void enqueue(queue<int>& q, int x, int y, vector<vector<char>> &board) 
    {
        if (x >= 0 && x < board.size() && y >= 0 && y < board[0].size() && board[x][y] == 'O')
        {
            q.push(x * board.size() + y);
        }
    }
};